############################
# author：码农小易
# blog：https://blog.csdn.net/csdn_xiaoyi
# 贪心算法尝试解找零钱
################################################################################################################
# 问题：
# 给出 i 种币值为 w 以及相应的数量 c ，
# 求解凑齐一定的金额 t 所用的最少的数量。
################################################################################################################

def go(need_back_change, denomination_list, count_list):
    min_count = 0                                               #统计最小所用纸币数量
    back_change = need_back_change                              #当前还需要找零的金额
    blocks = []
    for index, data in enumerate(denomination_list):            #将纸币的币值w与数量c绑定在一起，形成一个整体加入到blocks中
        blocks.append((data, count_list[index]))                #例子：[(1, 3), (2, 3), (5, 2), (10, 1), (20, 1), (50, 3), (100, 3)]

    blocks.sort(key=lambda x: x[0], reverse=True)               #以纸币的币值进行从高到低的排序
    
    for block in blocks:
        c = block[1]                                            #纸币数量
        d = block[0]                                            #纸币面值
        if (count := min(back_change // d, c)) > 0:             #判断能拿多少张面值为 d 的纸币，且拿的个数需要>0即能放入才能执行以下代码
            min_count += count                                  #统计拿了多少张
            if (back_change := back_change - d * count) == 0:   #如果找零过程中已经结束，则跳出循环
                break
    
    return min_count if back_change == 0 else -1                #由于使用贪心算法，可能存在零钱没法凑齐的情况，如果没法凑齐，则返回-1

################################################################################################################
# 并非所有情况能得出最优解：
# 存在零钱凑不起的问题。
################################################################################################################

def main():
    t = int(input('需要找零的金额：'))
    i = int(input('物品数量：'))
    print('i: ' + '  '.join([str(j+1) for j in range(i)]))
    w = list(map(int, input('w:').split()))
    c = list(map(int, input('c:').split()))

    print('min_count:', go(t,w,c))

if __name__ == "__main__":
    main()